1. Field of the Invention
The invention concerns virtual memory systems generally and particularly concerns techniques which make it easer to port an operating system which creates a virtual memory to different hardware environments.
2. Description of the Prior Art
Modern operating systems are generally multi-process virtual memory systems. Such operating systems create processes to execute programs. The operating system further creates a virtual address space for each process. Programs executed by the process specify data by means of virtual addresses. A virtual address specifies the location of the data in the process's virtual address space.
Of course, the operating system is executed on a physical computer system which has a physical memory system. The physical memory system is addressable by physical addresses. The operating system creates the virtual address space for a process by mapping those parts of the virtual address space to which virtual addresses currently employed by the process belong into portions of the physical memory system and then translating the virtual addresses into physical addresses specifying the data. The mapping is done in a data structure termed the page table. Modem computer systems often include a hardware component, the memory management unit, which employs information from the page table to accelerate the translation of virtual addresses into physical addresses.
Operating systems are generally adapted to run on a variety of different hardware systems. The operation of adapting an operating system to run on a different hardware system is termed porting the operating system to the hardware system. A goal of operating system designers is to reduce porting effort to a minimum. One area of the operating system which has always required substantial porting effort is the translation of virtual addresses to physical addresses. One reason why substantial effort has been required in this area is that the memory management unit of a given hardware system requires a specific form of page table. Since the page table is also used by the operating system, all of those components of the operating system which use the page table must be rewritten as required for the specific form of the page table. It is an object of the present invention to provide techniques which reduce the porting effort and otherwise reduce the cost of dealing with page tables.
Virtual Memory System Overview: FIGS. 1-3 PA0 Problems of Page Table 311: FIG. 4
FIG. 1 shows one of the processes created by the operating system and the virtual address space belonging to the process. Process (PROC) 107 has virtual address space (VAS) 101. To access data 105 in virtual address space 101, process 107 employs virtual address (VA) 109. Virtual address space 101 is subdivided into a number of virtual pages (VP) 103. Each virtual page 103 has a virtual page number (VPN) 104. A virtual address 109 consists of two parts: virtual page number 104 specifying the virtual page 103 which contains the data 105 and offset (OFF) 108 which specifies the offset of the data 105 from the beginning of the virtual page. Thus, if data 105 has offset 1024 in page 0, its virtual address is 01024.
Continuing with FIG. 2, that figure shows a hardware system 201 in which an operating system creates processes 107 and virtual address spaces 101. The main components of hardware system 201 are main processor (MP) 203, memory (MEM) 213, data store (DS) 217, and auxiliary processor (AP) 205. Auxiliary processor 205, memory 213, and main processor 203 are connected by bus 207.
Memory 213 is subdivided into physical pages (PP) 215. Each physical page has a physical page number 225, and data is referenced in memory 213 by means of a physical address 223 containing a physical page number 225 and the offset 108 of the data in the physical page. Virtual pages 103 are sized such that they are the same size as physical page 215 in memory 213. Consequently, a virtual address may be convened to a physical address by converting virtual page number 104 to physical page number 225 for the physical page 215 which contains data 105 and adding offset 108 from the virtual address to the physical page number.
Data store 217 is a mass storage device such as a disk drive which contains data 105 for a process 107 when process 107 is not actually referencing data 105. Data 105 is stored in a darn store page 219 which is the same size as virtual page 103 and physical page 215. Auxiliary processor 205 moves copies of data store pages 219 from data store 217 to physical pages 215 and moves copies of physical pages 215 in which data has been modified from memory 213 to data store pages 219.
Main processor 203 has two components which are of interest here: instruction execution unit 209, which executes instructions from a program in memory 213, and memory management unit 211. When an instruction specifies a virtual address 109, instruction execution unit 209 provides the virtual address 109 to memory management unit 211, which attempts to translate the virtual address 109 into the physical address of data 105 in memory 213. In so doing, it uses information in the page table. If data 105 is in memory 213, the translation succeeds, and memory management unit 211 provides physical address 223 to memory 213, which then accesses data 105.
If data 105 is not in memory 213, then a page fault results. The operating system responds to the page fault by determining which data store page 219 in data store 217 corresponds to virtual page 103 which contains data 105, copying that data store page 219 into a physical page 215, and updating the page table so that virtual page 103(x) specified in the virtual address 109 for the data is related to physical page 215(y) which to which the data store page 219 was copied. Once the page table has been updated, the memory management unit 211 again attempts the translation, which now succeeds.
FIG. 3 shows details of the page table and the relationship between the page table, virtual address space 101, the operating system, and memory management unit 211. Page table 311 is a data structure which contains page table entries 313. Each page table entry 313 relates a virtual page number 104 to the physical page number 225 for the physical page 215 which currently contains data whose addresses contain virtual page number 104. Page table entries 313 are referred to by memory management unit 211; they are also referred to by virtual memory manager 319. Virtual memory manager 319 is a program which is a component of the operating system. Virtual memory manager 319 responds to a page fault by copying data store page 219 corresponding to the referenced virtual page 103 into a physical page 215. In the course of doing this, virtual memory manager 319 updates page table 311 so that there is a page table entry relating the referenced virtual page to the physical page which contains the copy of data store to page 219.
Memory management unit 211 can only provide physical addresses 223 to memory 213; consequently, it must be able to reference page table 311 by means of physical addresses; virtual memory manager 319, on the other hand, is an operating system program, and as such, it uses virtual addresses; consequently, page table 311 must be located in an area of virtual memory where virtual addresses are the same as physical addresses. That area is of course the region of virtual address space 101 which begins at virtual address 0 (301 in FIG. 3) and extends to the virtual address which is the same as the maximum physical address 223, shown as 305. This portion of virtual address space 101 is reserved virtual address space (RVAS) 309, and is not available for addressing data other than page table 311.
An important consequence of the fact that page table 311 is referenced by memory management unit 211 is that memory management unit 211 dictates the form of page table 311, and that page table 311 is therefore a hardware-specific data, structure. FIG. 4 shows two possible versions of page table 311. Page table 311(a) is a page table array (PTA) 401. There are as many entries 403 in page table array 401 as there am virtual pages 103 in virtual address space 101. Each entry corresponds to one of the virtual pages and contains the physical page number 225 of physical page 215 corresponding to the virtual page, if such a physical page 215 currently exists.
Page table 311 (b) is a page table tree (PTT) 405. Page table tree 405 consists of a number of nodes 414. At the root of the page table tree is segment table node 407. Segment table node (STN) 407 specifies a set of segments of virtual address space 101. Each segment consists of a set of contiguous virtual pages. Segment table node 407 contains a segment table entry 409 for each segment. Each entry 409 contains the physical ass (shown by arrow 415) of a page table node 411 which contains page table entries 413 for the virtual pages 103 in the segment. Each page table entry 413 relates a virtual page number 104 to the physical page number 225 for the physical page (if any) which currently contains data addressed by virtual addresses 109 containing the virtual page number 104. Page table tree 405 is a two-level tree; level one 417 contains segment table node 407, while level 2 419 contains page table nodes 411. Page table nodes 411 are leaf nodes of page table tree 405. Page table trees 405 for other memory management units 211 may have more levels; the highest level always contains the leaf nodes with page table entries 413.
As can be seen by comparison of page table 311(a) with page table 311(b), the code in virtual memory manager 319 which manages page table array 401 will necessarily be different from the code in virtual memory manager 319 which manages page table tree 405; consequently, when the operating system is ported from a hardware system whose memory management unit 211 requires a page table array 401 to one which requires a page table tree 405, that portion of the code of virtual memory manager 319 must be rewritten. Similar rewrites are necessary to port the operating system from hardware which requires a two-level page table tree 405 to hardware which requires a page table tree 405 with more levels.
The arrangement shown in FIGS. 3 and 4 has additional problems. First, since page table 311 may be anywhere in memory 213, reserved virtual address space 309 must be as large as physical memory 213. In the past, physical memory 213 always had an address space which was much smaller than virtual address 101, so this requirement was not a problem. However, as memory has grown cheaper, physical memory has grown larger, so that reserved virtual address space 309 has become an ever more significant portion of virtual address space 101.
Second, page tables 311 are tending more and more to be implemented as page table trees 405 of three and more levels. There are two reasons for this. One, virtual addresses are getting longer, and consequently, the virtual address space 101 is getting larger. In the not-too-distant future, many hardware systems will employ 64-bit virtual addresses. Two, efficient use of memory 213 requires that physical pages 215 be relatively small. Since the size of the physical pages 215 determines the size of the virtual pages 103, the result of these two developments is that virtual address space 101 will contain ever more virtual pages 103. As the number of virtual pages increase, linear data structures like page table array 401 become more expensive and page table trees 405 acquire more and more levels. However, the more levels a page table tree 405 has, the slower and more complex the maintenance operations performed by virtual memory manager 319 become. For example, in a three-level tree, three memory references are required to locate a page table entry 413: one to locate segment table node 407, one to locate a second-level node, and one to locate the leaf node containing the page table entry 413.